package com.hy.day;

import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2244. 完成所有任务需要的最少轮数
 * 给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。
 * 返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。
 * User:Mr.Du
 * Date:2024/5/14
 * Time:10:24
 */
public class MinimumRounds {

    /**
     * 计算完成所有任务所需的最少轮数。
     * 每轮可以完成2个任务或者3个任务，
     * 贪心，尽可能多次完成3个任务，那么
     * n: 任务数
     * if n % 3 == 0, 则最少轮数为 n / 3
     * if n = 3 * k + 1 = 3 * k' + 4,其中 k' = k - 1 则最少轮数为 (n - 4) / 3 + 2 = (n + 2) / 3
     * if n = 3 * k + 2, 则最少轮数为 (n - 2) / 3 + 1 = (n + 1) / 3
     * 也就是整体下来，结果就是n / 3
     */
    public int minimumRounds(int[] tasks) {
        // 使用HashMap记录每个任务完成的次数
        Map<Integer, Integer> mp = new HashMap<>();
        int res = 0; // 记录最少轮数

        // 统计每个任务的完成次数
        for(int i : tasks) mp.put(i, mp.getOrDefault(i, 0) + 1);

        // 遍历每个任务的完成次数，计算最少轮数
        for(int e : mp.values()){
            if(e == 1) return -1; // 如果有任务只完成了一次，无法完成所有任务
//            if(e % 3 == 0) res += e / 3;
//            else if(e % 3 == 1) res += (e - 4) / 3 + 2;
//            else res += (e - 2) / 3 + 1;
            res += (e + 2) / 3;
        }
        return res;
    }


    /**
     * 定义dp数组，dp[i]表示i个任务需要的最少轮数
     */
    static int[] dp = new int[100001];
    static{
        dp[1] = -1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        for(int i = 5;i <= 100000;i++){
            dp[i] = Math.min(dp[i-2], dp[i-3]) + 1;
        }
    }
    public int minimumRounds1(int[] tasks) {
        Map<Integer, Integer> mp = new HashMap<>();
        int res = 0, cnt = 0;
        for(int i : tasks) mp.put(i, mp.getOrDefault(i, 0) + 1);
        int m = 0;
        for(Map.Entry<Integer, Integer> e : mp.entrySet()){
            int v = e.getValue();
            if(v == 1) return -1;
            res += dp[v];
        }
        return res;
    }
}
